package com.jxb.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 基数排序
 * 1：根据基数创建桶
 * 2：将个位数落到指定的桶中，对每个桶中的元素进行排序，根据排好序的元素调整原数组
 * 3：再将十位数落到指定的桶中，对每个桶中的元素进行排序，根据排好序的元素调整原数组
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] nums = {11,4222,322,6,0,4,25,933,4,2,61};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }


    public static int[] sortArray(int[] nums) {
        //先算出最大的位数，约定几轮排序
        int max = 0;
        for (int i = 0;i<nums.length;i++) {
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        //构建桶
        ArrayList<ArrayList<Integer>> indBuckets = new ArrayList<>();
        for (int i = 0;i<10;i++) {
            indBuckets.add(new ArrayList<>());
        }
        int mode = 10;
        int div = 1;
        //遍历，将每位数进行入桶
        for (int i = 0;i<maxDigit;i++,mode *= 10,div *= 10) {
            //将当前位数落入桶中
            for (int j = 0;j<nums.length;j++) {
                int num = (nums[j]%mode) / div;
                indBuckets.get(num).add(nums[j]);
            }
            /*看看桶中数据的分布*/
            for (int b = 0; b < indBuckets.size(); b++) {
                System.out.print("第"+b+"个桶包含数据：");
                System.out.println(indBuckets.get(b));
            }
            //桶中的数据写回原始数组，准备下一次的排序
            int index = 0;
            for (int j = 0; j < indBuckets.size(); j++) {
                ArrayList<Integer> subBucket = indBuckets.get(j);
                //对桶中的元素进行排序
                sortBucket(subBucket);
                for (Integer k:subBucket) {
                    nums[index] = k;
                    index++;
                }
                indBuckets.get(j).clear();
            }
        }
        return nums;
    }

    private static void sortBucket(ArrayList<Integer> subBucket) {
        if (subBucket.size() != 0) {
            //当前待排序的数据
            int currentValue;
            for (int i = 0;i<subBucket.size();i++) {
                //已被排序的数据索引
                int preIndex = i;
                //获取当前需要排序的数据
                if ((preIndex + 1)<subBucket.size()) {
                    currentValue = subBucket.get(preIndex + 1);
                    while (preIndex >= 0 && currentValue<subBucket.get(preIndex)) {
                        //将已排序的数据后退一位
                        subBucket.set(preIndex+1,subBucket.get(preIndex));
                        preIndex--;
                    }
                    subBucket.set(preIndex+1,currentValue);
                }
            }
        }
    }

}
